Target devices such as field programmable gate arrays (FPGAs), structured application specific integrated circuits (ASICs), and ASICs are used to implement large systems that may include million of gates and megabits of embedded memory. The complexity of a large system often requires the use of electronic design automation (EDA) tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) compilation flow is hardware description language (HDL) compilation. HDL compilation involves performing synthesis, placement, routing, and timing analysis of the system on the target device.
Clustering, also referred to as “packing”, is one procedure that is performed during HDL compilation. Clustering involves grouping basic logic elements onto resources of a target device. Clustering in an HDL compilation share objectives that are found in general cluster analysis such as the goal of grouping a set of objects in a manner that objects in a same group are more similar to each other than to those in other groups.
Traditional EDA tools perform clustering by utilizing a greedy algorithm that follows the problem solving heuristic of making a locally optimal choice at each stage with the hope of finding a global optimum. In many situations, the greedy algorithm does not produce an optimal solution, but instead yields locally optimal solutions. It has been observed that the solutions found for clustering problems would be influenced by the stalling points chosen for the greedy algorithm and earlier decisions made by the greedy algorithm.